/*
 * countingSort.cpp
 *
 *  Created on: Sep 9, 2012
 *      Author: jeffrey
 */
#include<iostream>
#include<limits>
#include "../header/util.h"
using namespace std;
class CountingSort{
public:
	static int* sort(int array[], int n){
		int max=numeric_limits<int>::min();
		int min=numeric_limits<int>::max();
		for(int i=0;i<n;i++){
			if(max<array[i])
				max=array[i];
			if(min>array[i])
				min=array[i];
		}
		int* map=new int[max-min+1]; // create counting map
		for(int i=0;i<n;i++){
			map[array[i]-min]++;
		}
		// accumulate counts
		for(int total=0,i=0;i<max-min+1;i++){
			int tmp=map[i];
			map[i]=total;
			total+=tmp;
		}
		// generate result array
		int *result=new int[n];
		for(int i=0;i<n;i++)
			result[map[array[i]-min]++]=array[i];
		return result;

	}
};



